package bintree.nowcode;

//根据前序遍历结果构建二叉树
import java.util.Scanner;

public class KY11 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            String str = scanner.next();
            TreeNode root = preOrderBuild(str);
            int index=0;

            inOrder(root);
            System.out.println();
        }
    }
    private static int index=0;
    private static TreeNode preOrderBuild(String str){
        char cur = str.charAt(index);
        if(cur == '#'){
            return null;
        }
        TreeNode root = new TreeNode(cur);
        index++;
        root.left=preOrderBuild(str);
        index++;
        root.right=preOrderBuild(str);

        return root;
    }

    private static void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    private static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(char val) {
            this.val = val;
        }

        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
